package uestc.lj.advanced.dp;

/**
 * 给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果
 *
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code07_PalindromeMinAdd {

	public static String getPalindrome1(String str) {
		if (str == null || str.length() < 2) {
			return str;
		}
		char[] charArray = str.toCharArray();

		int[][] dp = getDp(charArray);
		char[] res = new char[charArray.length + dp[0][charArray.length - 1]];
		int i = 0;
		int j = charArray.length - 1;
		int resleft = 0;
		int resright = res.length - 1;
		while (i <= j) {
			if (charArray[i] == charArray[j]) {
				res[resleft++] = charArray[i++];
				res[resright--] = charArray[j--];
			} else if (dp[i][j - 1] < dp[i + 1][j]) {
				res[resleft++] = charArray[j];
				res[resright--] = charArray[j--];
			} else {
				res[resleft++] = charArray[i];
				res[resright--] = charArray[i++];
			}
		}
		return String.valueOf(res);
	}

	/**
	 * dp[i][j]表示str[i...j]至少填几个使整体变成回文串
	 *
	 * @param str
	 * @return
	 */
	private static int[][] getDp(char[] str) {

		int[][] dp = new int[str.length][str.length];

		for (int j = 1; j < str.length; j++) {
			dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1;
			for (int i = j - 2; i > -1; i--) {
				if (str[i] == str[j]) {
					dp[i][j] = dp[i + 1][j - 1];
				} else {
					dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
				}
			}
		}
		return dp;
	}

	public static void main(String[] args) {
		String str = "AB1CD2EFG3H43IJK2L1MN";
		System.out.println(getPalindrome1(str));
	}
}
